---
id: 5900f4eb1000cf542c50fffd
title: 'Завдання 382: створення багатокутників'
challengeType: 1
forumTopicId: 302046
dashedName: problem-382-generating-polygons
---

# --description--

Багатокутник — це плоска фігура з прямих відрізків, які з’єднані таким чином, що формують замкнений ланцюг. Багатокутник складається з принаймні трьох сторін та не перетинається собою.

Множина додатних чисел $S$ утворює багатокутник $P$, якщо:

- немає двох сторін $P$ однакової довжини,
- довжина кожної сторони $P$ знаходиться в $S$, і
- $S$ не містить іншого значення.

Наприклад:

Множина {3, 4, 5} утворює багатокутник зі сторонами 3, 4 та 5 (трикутник).

Множина {6, 9, 11, 24} утворює багатокутник зі сторонами 6, 9, 11 та 24 (чотирикутник).

Множини {1, 2, 3} та {2, 3, 4, 9} не утворюють жодного багатокутника.

Розглянемо послідовність $s$, визначену наступним чином:

- $s_1 = 1$, $s_2 = 2$, $s_3 = 3$
- $s_n = s_{n - 1} + s_{n - 3}$ за умови $n > 3$.

Нехай $U_n$ буде множиною $\\{s_1, s_2, \ldots, s_n\\}$. Наприклад, $U_{10} = \\{1, 2, 3, 4, 6, 9, 13, 19, 28, 41\\}$.

Нехай $f(n)$ буде кількістю підмножин $U_n$, які утворюють принаймні один багатокутник.

Наприклад, $f(5) = 7$, $f(10) = 501$ та $f(25) = 18\\,635\\,853$.

Знайдіть останні 9 цифр в $f({10}^{18})$.

# --hints--

`generatingPolygons()` має повернути `697003956`.

```js
assert.strictEqual(generatingPolygons(), 697003956);
```

# --seed--

## --seed-contents--

```js
function generatingPolygons() {

  return true;
}

generatingPolygons();
```

# --solutions--

```js
// solution required
```
